package kmp;

/**
 * @author zhengTao
 * @version 1.0
 * @description: 实现 strStr()
 * @date 2022/10/22 13:55
 */
public class Demo28 {
    public static void main(String[] args) {
        //"mississippi"
        //"issip"
        String haystack= "mississippi";
        String needle= "issip";
        int i = strStr(haystack, needle);
        System.out.println(i);

    }
    public static int strStr(String haystack, String needle) {
        //根据子串，获取next数组
        int[] next=getNext(needle);
        int index=0;  //记录长串扫描的位置
        int j=0; //记录next数组扫描位置，也可以说字串扫描位置
        while (index<haystack.length()){
            if(haystack.charAt(index)==needle.charAt(j)){
                index++;
                j++;
            }else if(j>0){
                //从next[j] 位置开始扫描
                j=next[j-1];
            }else {
                //j=0,并且不匹配，长串位置加1
                index++;
            }
            //证明扫描到字串位置最后一个元素了，即完全匹配了，返回匹配开始位置
            if(j==needle.length()){
              return index-j;
            }
        }
        return -1;
    }

    private  static int[] getNext(String needle) {
        int[] next=new int[needle.length()];
        char[] chars = needle.toCharArray();
        //定义字串的坐标
        int j=0;
        //初始化next数组第一个位置为0
        next[0]=0;
        //从next数组第二个位置开始赋值
        for (int i = 1; i < chars.length; i++) {
            //如果j>0,防止出现负数
            while(j>0 && chars[i] != chars[j]){
                j = next[j-1];
            }
            if(chars[i] == chars[j]){
                next[i] = ++j;
            }
        }
        return next;
    }
    public static int strStr1(String haystack, String needle) {
        int[] next = getNext1(needle);
        char[] hay = haystack.toCharArray();
        char[] nee = needle.toCharArray();

        int i=0,j=0;
        while(i<haystack.length()){
            if(hay[i] == nee[j]){
                i++;
                j++;
            }else if(j>0){
                j = next[j-1];
            }else{
                i++;
            }
            if(j==needle.length()){
                return i-j;
            }
        }
        return -1;
    }
    /**
     * 获得next数组
     */
    public  static int[]  getNext1(String needle){
        int[] next = new int[needle.length()];
        char[] chars = needle.toCharArray();
        int j = 0;
        for(int i=1;i<needle.length();i++){
            while(j>0 && chars[i] != chars[j]){
                j = next[j-1];
            }
            if(chars[i] == chars[j]){
                next[i] = ++j;
            }
        }
        return next;
    }
}
